This invention relates generally to semiconductor memories and in particular to a memory, known as a content addressable memory, in which the data is accessed and modified based upon the content of the stored data.
A content addressable memory (CAM) semiconductor device is a well known device which permits the contents of the memory to be searched and matched instead of having to specify one or more particular memory location(s) in order to retrieve data from the memory. A CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. A CAM provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a database of 1000 entries may take ten separate search steps whereas a CAM device with 1000 entries may be search in a single operation resulting in a search which takes ten times less time. One example of an application in which CAM devices are often used is to store a routing table for high speed switching systems which need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
To better understand a CAM and its operation, the CAM structure and operation may be compared to conventional well-known random access memory (RAM) devices. A RAM device is an integrated circuit that temporarily stores data in an array of memory cells. In the RAM device, each stored piece of data may be accessed independently of any other piece of data. The data in a RAM is stored at a particular location called an address so that any piece of data in the RAM may be accessed by indicating the address at which the data is located. The RAM devices are often used for memory of a computer. Typical RAM devices may be organized as 262,144 memory locations (commonly called 256K) by four bits wide, or 1,048,576 memory locations (commonly called 1 Megabyte) by eight bits wide, but other different organizations also exist.
Typical RAM devices are composed of an array of memory cells wherein each memory cell may store a bit of information. Each memory cell may have one or more transistors depending on the type of RAM which may include a static RAM (SRAM) or a dynamic RAM (DRAM). A typical complementary metal on silicon (CMOS) implemented SRAM may have six transistors per memory cell in which four of the transistors are cross-coupled to store the state of the bit, and two transistors are used to alter or read out the state of the bit. For a SRAM, the state of the bit remains at one level or the other until deliberately changed or power is removed. DRAMs, on the other hand, have a dynamic storage unit which typically may include a single transistor and a capacitor which stores the bit information. During a read, the charge on the capacitor is drained to the bit line, requiring a rewrite of the bit, called a restore operation. Additionally, because the DRAM capacitor is not perfect, it loses charge over time, and needs to have its charge refreshed at regular intervals. Thus, dynamic memories are accompanied by controller circuits to rewrite the bit and refresh the stored charge on a regular basis.
A content addressable memory (CAM) device is organized differently from typical SRAM or DRAM devices. In particular, data in a CAM is stored in memory locations in a somewhat random fashion. The memory locations may be selected by an address bus or the data can be written directly into the first empty memory location because every location has a pair of special status bits that keep track of whether the location has valid information in it or is empty and therefore available for overwriting. As opposed to RAM devices in which information is accessed by specifying a particular memory location, once information is stored in a memory location of the CAM, it may be located by comparing every bit in the memory with data placed in a special register known as a compare register. If there is a match of every bit in particular memory locations with every corresponding bit in the register, a Match Flag is asserted to let the user know that the data in the register was found in the CAM device. A priority encoder may sort out which matching memory location has the top priority if there is more than on matching entry, and makes the address of the matching memory location available to the user so that the user may access the matching data. Thus, with a CAM device, the user supplies a piece of data he wants to match to the CAM and get back the address of any matching pieces of data in the CAM.
Known CAM devices are based on typical SRAM or DRAM memory cells that have been modified by the addition of extra transistors that compare the state of the bit stored in each memory cell with the state of a bit of a register. Logically, CAM devices perform an exclusive-NOR function so that a match is only indicated if both the stored bit and the corresponding register bit have the same state (i.e., xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d ). Generally, CAM devices use a ten transistor memory cell including a six transistor SRAM memory cell and four pull-down NMOS transistors which accomplish the exclusive-NOR functionality and the match line driving. These CAM devices using the ten transistor memory cell may have approximately a 70 to 180 nonosecond (ns) match time and a power dissipation of approximately 0.6 to 1.9 watts. These CAM devices may have sizes which are 256k and smaller since larger sizes may cause power dissipation problems. These CAM devices as described above, however, have a number of problems, drawbacks and limitations.
One drawback is that known CAM devices have very small storage capacities as compared to other memory devices, such as DRAM devices and SRAM devices. These smaller storage capacities are due to the fact that the CAM storage size is principally limited by the large amount of power dissipated by each match line in the CAM. Each match line may have one or more NMOS pull-down transistor associated with it so that for a CAM having 4096 memory locations, a match request causes power dissipation from 4095 match lines transistors since all of the non-matching match lines output low signals. e.g., logic 0. Therefore the associated NMOS pull-down transistors will dissipate power. Another drawback is that attempts to increase the speed performance of conventional CAM devices causes other problems since the faster CAM device leads to increased power dissipation. The problem is that the power dissipation cannot be increased very much without exceeding maximum power dissipation levels. Thus, conventional CAM devices are limited in size and performance because of the power being dissipated by the transistors associated with the match lines.
Another drawback of conventional CAM devices is that the memory devices themselves do not have much built-in intelligence or management functions so that, for each new operation environment, a piece of software must be written which is then responsible for management of the functions of the CAM device. The CAM management functions may include disabling unused CAM memory cells, maintaining a list of available CAM memory cells and checking for and avoiding insertion of duplicate data in more than one CAM memory cell.
Thus, it is desirable to provide a content addressable memory which overcomes the above described drawbacks, problems and limitations of conventional CAM devices and it is to this end that the present invention is directed.
In accordance with the invention, a CAM cell architecture is provided which overcomes the above problems of conventional CAM devices. In particular, a new architecture for each CAM cell is provided which uses a new and different compare cell structure. The new structure may employ CMOS transistors and have a wide AND gate structure which provides significant advantages over and eliminates the power dissipation problems in conventional CAMs. In particular, the new architecture permits the size and speed of the CAM to be independent of the match line power dissipation, since it eliminates the match lines. In a CAM device of the invention, the match time is substantially improved. It is determined by the bit line drivers and the delay due to routing capacitance and gate delays, which results in match times comparable to current state of the art SRAM devices (approximately 7 ns) instead of the typical 50 ns match time for conventional CAM devices. In addition, since the new architecture reduces the power dissipation by the elimination of the match lines, the size of the CAM device of may increase significantly (e.g., by up to ten times the current size of conventional CAMs).
The CAM device of the invention also permits CAM cells to be stacked on top of each other in a novel layout. Multiple CAM cells may be easily stacked together to form CAM devices which are more dense than conventional CAM devices. In addition, the CAM may be dynamically reconfigurable to change the width and length of the CAM array and partition the memory between the CAM cells and the RAM cells. The CAM also has an improved management interface, an improved multiple match resolution circuitry, and a match queue for enhanced handling of multiple matches.
In accordance with the invention, a content addressable memory device is provided which has a content addressable memory element. The content addressable memory element comprises a memory cell that stores a bit and a compare cell that compares the bit in the memory cell to a compare bit and generates an output signal indicating whether the bit matches the compare bit. The device further comprises a logic gate that combines the outputs from the content addressable memory element with other content addressable memory elements to generate a signal indicating a matching entry in the content addressable memory device if the compare bits match the bits stored in the content addressable memory elements. The logic gate is geographically distributed throughout the content addressable memory device.
In accordance with another aspect of the invention, a content addressable memory device is provided. The device comprises a content addressable memory array comprising a plurality of content addressable memory elements. Each content addressable memory element comprises a memory cell that stores a bit and a compare cell that compares the bit in the memory cell to a compare bit and generates an output signal indicating whether the bit matches the compare bit. The device further comprises a logic gate that combines; the output of the compare cell from each content addressable memory element to generate a signal indicating a matching entry in the content addressable memory device if the compare bits match the bits stored in the content addressable memory elements.